\documentclass{article}
\input{macro.tex}
\title{A matrix problem}
\begin{document}
\maketitle
Consider a matrix $\Phi$
$$
\Phi = \begin{pmatrix}
\phi_1 \\
\phi_2 \\
\dots \\
\phi_d
\end{pmatrix}
$$
where $\phi_i$ is a $k_i \times k$ matrix. Assume $k> \max\{k_1,\dots, k_d\}$. Let $\phi_i \phi^T_j = B_{ij}$ where $B_{ij}$ is given.
We try to minimize $\frac{1}{2} \sum_{i=1}^d \norm{\phi_i}_F^2$ where $\norm{\cdot}_F$ is Frobenius norm of matrix.

When $d=2$, the minimum is summation of all singular values of $B_{12}$, which is called the kernel norm of $B_{12}$, denoted by $\norm{B_{12}}_*$. It can be shown as follows:

Let $B_{12} = U \Sigma V $ be the singular value decomposition of $B_{12}$ where $\Sigma$ is a diagonal matrix. Let $\tilde{\phi}_1 = U^{-1}\phi_1, \tilde{\phi}_2 = V\phi_2 $, then $\Sigma = \tilde{\phi}_1 \tilde{\phi}^T_2$. Since orthogonal transformation does not change the Frobenius norm of matrix, it is equivalent to minimize $\frac{1}{2} (\norm{\tilde{\phi}_1}_F^2 + \norm{\tilde{\phi}_2}_F^2)$.

Let $r=\mathrm{rank}(\Sigma)\leq \min\{k_1, k_2\}, \Sigma' = \Sigma_{r,r}$ which is the block square matrix of $\Sigma$ with first $r$ rows and columns. Also let $\tilde{\phi}_{ir}$ be the first $r$ rows of $\tilde{\phi}_{i}(i=1,2)$. Then $\Sigma_r = \tilde{\phi}_{1r}\tilde{\phi}^T_{2r}, \tr(\Sigma_r)=\tr(\Sigma)$.

From $\norm{\tilde{\phi}_{1r}-\tilde{\phi}_{2r}}\geq 0 \Rightarrow \frac{1}{2} (\norm{\tilde{\phi}_1}_F^2 + \norm{\tilde{\phi}_2}_F^2) \geq \frac{1}{2} (\norm{\tilde{\phi}_{1r}}_F^2 + \norm{\tilde{\phi}_{2r}}_F^2)  \geq \tr(\tilde{\phi}_{1r} \tilde{\phi}^T_{2r}) = \tr(\Sigma)$. Therefore the conclusion holds. The equality is taken when the $j$-th row of $\tilde{\phi}_{i}$ is zero vector for $i=1,2$ and $j>r$. And $\phi_1 = U \sqrt{\Sigma_1} Q, \phi_2 = V^{-1} \sqrt{\Sigma_2} Q$ where $Q$ is $r\times k$ matrix and satisfies $QQ^T= I_r$ (identity matrix with $r$ dimension). Let $\Sigma_r = \diag\{\sigma_1, \dots, \sigma_r\}$. $\sqrt{\Sigma_i}$ is a $k_i \times r $ matrix whose $(j,j)$ entry is $\sigma_j$ for $j\leq r$ and other entry is zero.
\end{document}